#include <stdio.h>

int MaxSubseqSum1(int A[], int N);
int MaxSubseqSum2(int left, int right, int a[]);
int MaxSubseqSum3(int A[], int N);

int main()
{
    int b[10] = {1, 2, -3, 4, 5, 6, 7, -8, 9, -10};
    int max1 = MaxSubseqSum1(b, 10);
    int max2 = MaxSubseqSum2(0, 9, b);
    int max3 = MaxSubseqSum3(b, 10);
    printf("%d %d %d", max1, max2, max3);
    return 0;
}
// 最大子列和问题
// 算法1：暴力求解
int MaxSubseqSum1(int A[], int N)
{
    int ThisSum = 0, MaxSum = 0;
    for (int i = 0; i < N; i++) // i是子列左端位置
    {
        ThisSum = 0;
        for (int j = i; j < N; j++) // j是子列右端位置
        {
            ThisSum += A[j];
            // 对于相同的i，不同的j，只要在j-1循环的基础上累加一项即可
            /* for (int k = i; k <= j;k++)
            {
                ThisSum += A[k];
            } */
            // 实际上，这里面的一串循环是不必要的
            if (ThisSum > MaxSum)
                MaxSum = ThisSum;
        }
    }
    return MaxSum;
}
// 复杂度为T（n） = O（n^2）  能不能更简单一点呢？.......算法2！

/*算法2：分而治之
将一个问题一分为二，先解决左半边，再解决右半边，最后解决跨边界的，再将三个结果比较*/
int MaxSubseqSum2(int left, int right, int a[])
{
    // 首先需要判断子列的边界是否符合要求
    if (left == right)
    {
        return a[left]; // 这个子列就这一个数
    }
    // 如果还可以继续分，就接着执行下面的代码
    int center = (left + right) / 2;
    int leftMax = MaxSubseqSum2(left, center, a);
    int rightMax = MaxSubseqSum2(center + 1, right, a); // 第一次写时，这里的left参数写成了center（没有加一）产生了栈溢出的问题。是为什么呢？？？
    // 算到后面，center一直没变，所以left和right一直不相等，最终无限调用函数。

    // 然后开始考虑跨线的情况
    int sum = a[center] + a[center + 1];
    int tepsum = sum;
    for (int i = center - 1; i >= left; i--) // 左边
    {
        tepsum += a[i];
        if (tepsum > sum)
            sum = tepsum;
    }
    tepsum = sum; // 重置tepsum
    for (int j = center + 2; j <= right; j++)
    {
        tepsum += a[j];
        if (tepsum > sum)
            sum = tepsum;
    }
    // 最后将三个结果进行比较
    if (leftMax > sum)
        sum = leftMax;
    if (rightMax > sum)
        sum = rightMax;
    return sum;
}

// 还能不能更快一点？！
// 有的兄弟，有的。这个算法3叫做在线处理
int MaxSubseqSum3(int A[], int N)
{
    int ThisSum = 0, MaxSum = 0;
    int i;
    for (i = 0; i < N; i++)
    {
        ThisSum += A[i];
        if (ThisSum > MaxSum)
            MaxSum = ThisSum;
        else if (ThisSum < 0) // 如果当前子列和为负，则不可能使后面的部分和增大，则舍弃这种情况。
            ThisSum = 0;
    }
    return MaxSum;
}
